#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

const int MAX = 70;

int flag[MAX];
int stick[MAX];

int target, n;	// 要拼的木棍长度，一共有多少根小木棍

/*
 * now: 拼当前木棍正在使用的小木棍的编号;
 * rest: 还剩下多少小木棍没有使用
 * now_len: 当前正在拼的木棍已经拼了多长
 * count: 当前已经完成了多少根木棍
 */
int merge(int now, int rest, int now_len, int count)
{
	if(rest == 0)
		return 1;

	if(now_len == target)
	{
		now_len = 0;
		count++;
		now = 0;
		for(;flag[now];++now)
			;
		// 优化3: 最长的count根木棍肯定会被前count个整个木棍用掉
		if(now < count)
			return 0;
	}

	for(int i = now;i<n;++i)
	{
		if(flag[i])
			continue;

		// 优化1: 如果前一根相同长度的木棍没有被使用，则本根也不使用
		if(i && stick[i] == stick[i-1] && !flag[i-1])
			continue;

		flag[i] = 1;
		// 优化4: 拼每一根木棍的时候，总是从刚拼过木块的编号的下一个开始
		if(target - now_len >= stick[i] && merge(i + 1, rest - 1, now_len + stick[i], count))
			return 1;
		flag[i] = 0;
	}

	return 0;
}

bool cmp(const int a, const int b)
{
	return a > b;
}

int main()
{
	int sum;
	while(scanf("%d", &n) != EOF && n)
	{
		sum = 0;
		for(int i = 0;i<n;i++)
		{
			scanf("%d", &stick[i]);
			sum += stick[i];
		}

		// 优化0: 将小木棍按长度从大到小排序
		sort(stick, stick + n, cmp);

		for(int i = stick[0];;i++)
		{
			// 优化2: 不考虑大于sum/2的长度
			if(i > (sum >> 1))
			{
				printf("%d\n", sum);
				break;
			}
			if(sum % i)
				continue;
			memset(flag, 0, sizeof(flag));
			target = i;
			if(merge(0, n, 0, 0))
			{
				printf("%d\n", i);
				break;
			}
		}
	}
}
